/*
 * Saphre - Suffix Arrays for Phrase Extraction
 * Copyright (C) 2013 
 * Dale Gerdemann - Tübingen, Germany 
 * Niko Schenk - Frankfurt am Main, Germany
 * All rights reserved.
 *
 * This program is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 * details.
 *
 * You should have received a copy of the GNU General Public License along with
 * this program. If not, see <http://www.gnu.org/licenses/>.
 *
 */
package saphre.concordance;

import util.Interval;
import saphre.core.Store;
import saphre.core.SuffixArray;
import util.Array;
import util.IntString;
import util.IntTST;

import java.io.Serializable;

/**
 * 
 * @author Dale Gerdemann
 */
public class ConcordanceOverlap implements Serializable {

    boolean filter;
    String target;
    int[] targetArray;
    Store store;
    int N;
    int Z = 18;  // indentation
    int state = 0;
    int[] empty = new int[0];
    int[] prevLeftArr = empty;


    /**
     * 
     * @param a1
     * @param a2
     * @return 
     */
    public boolean arrayEq(int[] a1, int[] a2) {
        if (a1.length != a2.length) {
            return false;
        }
        for (int i = 0; i < a1.length; i++) {
            if (a1[i] != a2[i]) {
                return false;
            }
        }
        return true;
    }

    /**
     * 
     * @param store 
     */
    public ConcordanceOverlap(Store store) {
        // this.tc = tc;
        this.store = store;
        // Context.store = store;
        N = store.text.length - 1;
        this.Z = Z + 20;
        // filter = true;
    }

    /**
     * 
     * @param target 
     */
    public void setTarget(String target) {
        this.state = 0;
        this.target = target;
    }

    /**
     * 
     * @param targetArray 
     */
    public void setTargetArray(int[] targetArray) {
        this.targetArray = targetArray;
    }

    /**
     * 
     * @param inter
     * @param lcp
     * @param pa
     * @param targetLcp
     * @param sa
     * @return 
     */
    public IntTST traverse(Interval inter, int lcp, SuffixArray pa,
                    int targetLcp, SuffixArray sa) {
        if (inter.trivial()) {
            return new IntTST();
        }
        else {
            int mid = inter.mid(pa.getCldtab());
            int midLcp = inter.lcp(mid, pa.getLcptab());

            int increase = 0;
            if (lcp < midLcp) {
                increase = midLcp - lcp;
            }
            int top = pa.getSuftab()[mid];
            int bot = top - midLcp + 1;

            boolean reject = false;
           
            IntTST st1 = new IntTST();
            IntTST st2 = new IntTST();
            if (!reject) {
                Interval left = new Interval(inter.lb(), mid - 1);
                Interval right = new Interval(mid, inter.rb());
                st1 = traverse(left, midLcp, pa, targetLcp, sa);
                st2 = traverse(right, midLcp, pa, targetLcp, sa);
            }

            if (st1.size() < st2.size()) {
                for (IntString s : st1.keys()) {
                    st2.put(s);
                }

            }
            else {
                for (IntString s : st2.keys()) {
                    st1.put(s);
                }
            }

            if (!reject && increase > 0 && midLcp >= targetLcp) {

                int begin = bot;
                int length = midLcp;
                String cache = store.toStringL(begin, length - targetLcp);
                int[] leftArr = store.toArrayL(begin, length - targetLcp);
                Interval rInterval = sa.search(store.toArrayL(begin, length));
                boolean success = traverse2(rInterval, midLcp - 1, sa, pa, cache, midLcp, st2, leftArr);
                // if (!success) {
                // System.out.printf("%"+Z+"s  %s\n", cache, target);
                // }
            }
            return st2;
        }
    }

    /**
     * 
     * @param inter
     * @param lcp
     * @param sa
     * @param pa
     * @param leftPart
     * @param rLcp
     * @param st
     * @param leftArr
     * @return 
     */
    public boolean traverse2(Interval inter, int lcp, SuffixArray sa, SuffixArray pa, String leftPart,
                      int rLcp, IntTST st, int[] leftArr) {
        if (inter.trivial()) {
            return false;
        }
        else {
            boolean success = false;

            int mid = inter.mid(sa.getCldtab());
            int midLcp = inter.lcp(mid, sa.getLcptab());
            int increase = 0;
            if (lcp < midLcp) {
                increase = midLcp - lcp;
            }
            int top = sa.getSuftab()[mid];
            int bot = top + midLcp;
            boolean reject = false;

            if (!reject && increase > 0) {
                int[] pat = store.toArray(top + rLcp, bot);
                if (!st.contains(pat)) {
                    success = true;
                    st.put(pat);
                    int lLen = leftArr.length;
                    int rLen = bot - top - rLcp;

                    String mark = "x";
                    if (state == 0) {
                        if (rLen == 0) {
                            if (lLen == 0) {
                                state = 2;
                                prevLeftArr = empty;
                            }
                            else {
                                state = 1;
                                prevLeftArr = leftArr;
                            }
                        }
                    }
                    else if (state == 1) {
                        if (rLen > 0) {
                            if (arrayEq(leftArr, prevLeftArr)) {
                                mark = "*";
                            }
                            else {
                                prevLeftArr = leftArr;
                                state = 0;
                            }
                        }
                        else if (lLen > 0) {
                            state = 1;
                            prevLeftArr = leftArr;
                        }
                    }
                    else {
                        state = 2;
                    }
                    if (mark.equals("*")) {

                        int[] full = Array.plus(targetArray,
                                store.toArray(top + rLcp,
                                        bot));

                        if (sa.isMaximal(full, sa.top, sa, pa, store)) {
                            System.out.printf("%" + Z + "s  %s   %s\n",
                                    leftPart, target,
                                    store.toString(top + rLcp,
                                            bot));
                        }
                    }
                }
            }
            boolean success1 = false;
            boolean success2 = false;
            if (!reject) {
                Interval left = new Interval(inter.lb(), mid - 1);
                Interval right = new Interval(mid, inter.rb());
                success1 = traverse2(left, midLcp, sa, pa, leftPart, rLcp, st, leftArr);
                success2 = traverse2(right, midLcp, sa, pa, leftPart, rLcp, st, leftArr);
            }
            return (success || success1) || success2;
        }
    }
}